#TM.rb 2019.10.24
module UTuringMachine
  class Tape < Struct.new(:left, :down, :right, :blank)
      def to_s    = "#<Tape #{left.join}(#{down})#{right.join}>"
      def inspect = "#<Tape #{left.join}(#{down})#{right.join}>"

      def none_move  = self
      def right_move = Tape.new(left + [down], right.first || blank, right.drop(1), blank)
      def left_move  = Tape.new(left[0..-2], left.last || blank, [down] + right, blank)

      def write(character) = Tape.new(left, character, right, blank)
  end

  # tape = Tape.new(['1', '0', '1'], '1', ['1'], '_')
  # puts tape.left_move.write('0')
  # puts tape.right_move.right_move.right_move

  class TMConfiguration < Struct.new(:state, :tape)
  end

  class TMRule < Struct.new(:current_state, :character, :next_state, :write_character, :direction)
      def apply_to?(configuration)
          @current_state == configuration.state && @character == configuration.tape.down
      end
  end

  # rule = TMRule.new(1, '0', 2, '1', :right)
  # puts rule.apply_to?(TMConfiguration.new(1, Tape.new([], '0', [], '_')))
  # puts rule.apply_to?(TMConfiguration.new(2, Tape.new([], '0', [], '_')))
  # puts rule.apply_to?(TMConfiguration.new(2, Tape.new([], '1', [], '_')))

  class TMRule
      def follow(configuration)
          TMConfiguration.new(next_state, next_tape(configuration))
      end
      def next_tape(configuration)
          written_tape = configuration.tape.write(write_character)
          case direction
          when :left
              written_tape.left_move
          when :right
              written_tape.right_move
          when :none
              wirtten_tape.none_move
          end
      end
  end

  # rule = TMRule.new(1, '0', 2, '1', :right)
  # puts rule.follow(TMConfiguration.new(1, Tape.new([], '0', [], '_')))

  class DTMRulesbook < Struct.new(:rules)
      def next_configuration(configuration)
          rules_for(configuration).follow(configuration)
      end
      def rules_for(configuration)
          rules.detect {|rule| rule.apply_to?(configuration)}
      end
  end

  class DTM < Struct.new(:current_configuration, :accept_states, :rulesbook)
      def accepting?
          @accept_states.include?(current_configuration.state)
      end
      def step
          @current_configuration = @rulesbook.next_configuration(current_configuration)
      end
      def run
          step until accepting?
      end
  end

  rulesbook = DTMRulesbook.new([
      TMRule.new(1, '0', 2, '1', :right),
      TMRule.new(1, '1', 1, '0', :left),
      TMRule.new(1, '_', 1, '1', :right),
      TMRule.new(2, '0', 2, '0', :right),
      TMRule.new(2, '1', 2, '1', :right),
      TMRule.new(2, '_', 3, '_', :left)
  ])

  # dtm = DTM.new(TMConfiguration.new(1, Tape.new(['1', '0', '1'], '1', [], '_')), [3], rulesbook)
  # dtm.run; puts dtm.current_configuration; puts dtm.accepting?

  class DTMRulesbook
      def apply_to?(configuration)
          !rules_for(configuration).nil?
      end
  end

  class DTM
      def stuck?
          !rulesbook.apply_to?(current_configuration) && !accepting?
      end
      def run
          step until accepting? || stuck?
      end
  end

  # dtm = DTM.new(TMConfiguration.new(1, Tape.new(['1', '2', '1'], '1', [], '_')), [3], rulesbook)
  # dtm.run; puts dtm.current_configuration; puts dtm.accepting?

end
